![image](http://habr.habrastorage.org/post_images/f36/b14/d1c/f36b14d1cbf97894d40b1acc30e0c15f.png)
Вот пример процедуры построения кучи по массиву на языке Pascal.
procedure siftdown(v:longint); var min,l,r:longint; begin l:=v*2; r:=v*2+1; min:=v; if (l <= s) and (a[l] < a[min]) then min:=l; if (r <= s) and (a[r] < a[min]) then min:=r; if min <> v then begin swap(a[min], a[v]); sift_down(min); end; end; procedure build; var i:longint; begin for i:=n downto 1 do siftdown(i); end;
Итак, пусть дан массив, состоящий из элементов, и
количество вызовов оператора
(в процедуре
) при построении кучи по этому массиву. Очевидно,
определяет время работы процедуры
, которое нам и интересно.
Лемма.
Пусть для какого-то элемента массива при вызове было сделано
вызовов оператора
. Тогда его индекс не превосходил
.
Доказательство:
При вызовах оператора
индекс
элемента возрастает как минимум в
раз. Пусть теперь
, т.е.
. Тогда после
вызовов имеем
, что невозможно, так как в нашей куче
элементов.
Оценим теперь сверху величину . Пусть элемент массива имеет индекс
. Найдется
, такое что
. Тогда для того, чтобы элемент массива с индексом
встал на свое место в куче потребуется не больше
вызовов
(по лемме). Количество элементов с такими индексами есть величина
, которая при
обращается в нуль.
Таким образом,
При слагаемые нулевые(поэтому цикл в процедуре
можно начинать с
).
Оценим левый множитель в каждом слагаемом суммы, как
Отсюда имеем:
Оценим каждую из сумм.
Таким образом, .
ограничена сверху и снизу функциями, которые есть
. Значит,
.
Следовательно, время работы процедуры есть величина пропорциональная
.
ссылка на оригинал статьи http://habrahabr.ru/post/195832/
Добавить комментарий